/**
https://leetcode.cn/problems/sliding-puzzle/description/
773. 滑动谜题
 Medium, 方钊堉 2024.12.07
 BFS
 */

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        // 用于存储已经访问过的棋盘状态，避免重复访问
        unordered_set<string> visited;
        // BFS 队列，存储当前的棋盘状态
        queue<vector<vector<int>>> q;
        // 四个方向的移动：上、下、左、右
        vector<pair<int, int>> moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        // 目标状态
        vector<vector<int>> target = {{1, 2, 3}, {4, 5, 0}};
        
        // 将初始状态加入队列和访问集合
        q.push(board);
        visited.insert(boardToString(board));

        int steps = 0; // 记录步数

        while (!q.empty()) {
            int layerSize = q.size(); // 当前层的节点数量

            for (int i = 0; i < layerSize; ++i) {
                vector<vector<int>> current = q.front();
                q.pop();

                // 如果当前状态是目标状态，返回步数
                if (current == target) {
                    return steps;
                }

                // 找到空格（0）的位置
                pair<int, int> zeroPos;
                for (int r = 0; r < 2; ++r) {
                    for (int c = 0; c < 3; ++c) {
                        if (current[r][c] == 0) {
                            zeroPos = {r, c};
                            break;
                        }
                    }
                }

                // 尝试四个方向的移动
                for (auto& move : moves) {
                    int newRow = zeroPos.first + move.first;
                    int newCol = zeroPos.second + move.second;

                    // 检查新位置是否在棋盘范围内
                    if (newRow >= 0 && newRow < 2 && newCol >= 0 && newCol < 3) {
                        // 创建新的棋盘状态
                        vector<vector<int>> newState = current;
                        // 交换空格和相邻位置的数字
                        swap(newState[zeroPos.first][zeroPos.second], newState[newRow][newCol]);

                        // 将新的棋盘状态转换为字符串，方便查找
                        string stateStr = boardToString(newState);

                        // 如果新的状态未访问过，加入队列并标记为已访问
                        if (visited.find(stateStr) == visited.end()) {
                            q.push(newState);
                            visited.insert(stateStr);
                        }
                    }
                }
            }

            ++steps; // 每处理完一层，步数加 1
        }

        return -1; // 无法到达目标状态，返回 -1
    }

private:
    // 将棋盘状态转换为字符串，方便存储和查找
    string boardToString(const vector<vector<int>>& board) {
        string result;
        for (const auto& row : board) {
            for (int num : row) {
                result += to_string(num);
            }
        }
        return result;
    }
};